This invention relates to the field of modeling interactions, specifically modeling interactions among complex polyhedra in motion.
Many robotics applications require modeling of interactions. For example, collision detection is a basic problem in robotics and related areas, arising in motion planning, control, graphical programming, motion-preview, virtual reality, and dynamical simulation. The collision detection problem asks whether a rigid body moving along a given path intersects with any of a set of obstacles at any point on that path. In a fuller version of the problem, all contacts must also be determined. In both cases, accuracy is of extreme importance when the results of collision detection between modeled objects affect the behavior of physical robots or influence the outcomes of physical simulations, such as those used in process and product design and evaluation.
Most current methods for collision detection rely on interference detection or distance computation. A few recent algorithms are very fast, using queries at steps in the bodies"" motion. However, the difficulty of determining collisions or distances between steps mandates the use of very small step sizes, consequently reducing efficiency.
Interference detection (or collision detection) for a rigid body R at a position and orientation x and obstacles O means to determine whether R(x)∩ O is non-empty, with R(x) denoting the image of R in the world. Distance computation means to determine the minimum distance between all points in R(x) and those in O. Simple collision detection for a rigid body R moving over a path segment among obstacles O means to determine whether at any point along the path the body contacts or intersects any obstacles. In other words, if we let C denote the space of positions and orientations and let p: [0,1] xe2x86x92 C denote the path segment, then collision detection asks whether there is any t xcex5[0,1] such that R(p(t)) ∩ O is non-empty.
Exact or accurate collision detection is often avoided for the sake of speed. Usually, either interference detection or distance computation queries are applied at closely spaced points on the path. Simple use of interference detection can miss collisions. Growing the objects by a safety margin can prevent this, but at the risk of detecting false collisions. With distance computation, one can vary the step size to reduce the number of queries needed to obtain a given resolution, but resolution is limited by the minimum step size.
For a number of years, hierarchical geometric representations have been used to avoid xe2x80x9call pairsxe2x80x9d comparisons in interference detection, distance computation, and collision detection. The binary-space partitioning tree (BSPtree) and variants have been successfully used in exact interference checking and contact determination, but they do not readily yield distance information. See, e.g., Fuchs et al., xe2x80x9cOn visible surface generation by a priori tree structures,xe2x80x9d Proc. of ACM SIGGRAPH, pages 124-133, 1980. The octree is another space-partitioning data-structure that has been used in interference detection, but it must be used with other geometric objects to obtain computations matching the accuracy of faceted boundary representations or BSP-trees. See, e.g., Jackins et al., xe2x80x9cOctrees and their use in representing three-dimensional objects,xe2x80x9d Computer Graphics and Image Processing, (14):249-270, 1980; Meagher, xe2x80x9cGeometric modeling using octree encoding,xe2x80x9d Computer Graphics and Image Processing, (19): 129-147, 1982.
Other hierarchical structures use various primitives to bound an object or its surface at each level of the hierarchy, although sometimes holes are treated explicitly. See, e.g., Faverion, xe2x80x9cHierarchical object models for efficient anti-collision algorithms,xe2x80x9d Proc. IEEE ICRA 1989, pages 333-340, Scottsdale, Ariz. 1989. Successful implementations for exact interference detection and distance computation have been based on several geometric primitives. Convex-hull based implementations, sphere-based techniques, and bounding-prism methods are among those known to be fast. See, e.g., Cameron, xe2x80x9cDealing with geometric complexity in motion planning,xe2x80x9d IEEE ICRA 1996 Workshop on Practical Motion Planning in Robotics,xe2x80x9d Minneapolis, Minn. 1996; Quinlan, xe2x80x9cEfficient distance computation between non-convex objects,xe2x80x9d Proc. 1994 IEEE Int""l Conf on Robotics and Automation, San Diego, Calif. 1994; Sato et al., xe2x80x9cEfficient collision detection using fast distance calculation algorithms for convex and non-convex objects,xe2x80x9d Proc. 1995 IEEE Int""l Conf on Robodcs and Automation, pages 772-778, Minneapolis, Minn. April 1996; Gottschalk et al., xe2x80x9cOBB-tree: A hierarchical structure for rapid interference detection,xe2x80x9d Proc ACM SIGGRAPH""90, 1996. However, none of these results cover swept-body distance or swept-body interference detection.
Canny described a technique for exact collision detection for convex polyhedra moving along path segments linear in translation and the quaternion representation of SO(3). See Canny, xe2x80x9cCollision detection for moving polyhedra,xe2x80x9d IEEE Trans. on Pattern Analysis and Machine Intelligence, 8(2):200-209, 1986. Finally, Cameron used space-time techniques and develops algorithms and hierarchical structures for exact collision detection for non-convex objects. See Cameron, xe2x80x9cCollision detection by 4D intersection testing,xe2x80x9d Int""l Journal of Robotics Research, 6(3):291-302, June 1990. Both these results are general in allowing exact time intervals of contact and penetration to be computed directly. Canny, however, only computes interactions between convex objects. Cameron describes a theoretical method for objects modeled by Boolean constructive solid geometry (CSG) trees and an implemented method of objects modeled by Boolean CSG trees with linear half-spaces at their leaves. The implemented method of Cameron is complicated and might be computationally expensive for a large class of non-convex objects, particularly those whose CSG models include difference operator. Neither Canny nor Cameron provides computation of the minimal clearance distance between bodies that do not collide.
Current technology thus provides two options, even when the motions are linear translations: (i) distance computation or interference detection between moving objects at discrete points in time; and (ii) exact collision detection in space-time without clearance distances that has limitations with regard to non-convex objects. The first option often requires very small motion steps for robustness (e.g., to not miss collisions), which causes a performance penalty in simulations, motion planning, graphical programming, and motion inspection. It is not an option when the motion step-size cannot be arbitrarily controlled, which is the case with currently available virtual reality motion-capture systems. Because many objects in the world are non-convex, the second option is of limited use in the applications mentioned above. Furthermore, the lack of robust minimal clearance distance computation during motion limits what is feasible in safety analyses.
There is therefore a need for a method and apparatus for modeling interactions between moving bodies that is faster and more robust than current approaches.
The present invention provides a method and apparatus for modeling interactions that overcomes drawbacks of the prior approaches. The method of the present invention comprises representing two bodies undergoing translations by two hierarchical swept volume representations. Interactions such as nearest approach and collision can be modeled based on the swept body representations. The present invention is computationally fast and robust, and relatively simple to implement. It can serve as a practical tool in motion planning, CAD systems, simulation systems, safety analysis, and applications that require modeling time-based interactions.
A body can be represented in the present invention by a union of convex polygons and convex polyhedra. The body undergoing translation can then be represented by a swept body representation, where the swept body representation comprises a hierarchical bounding volume representation whose leaves each contain a representation of the region swept by a section of the body during the translation, and where the union of the regions is a superset of the region swept by the surface of the body during translation. Interactions between two bodies thus represented can be modeled by modeling interactions between the convex hulls of the finite sets of discrete points in the swept body representations.
Advantages and novel features will become apparent to those skilled in the art upon examination of the following description or may be learned by practice of the invention. The objects and advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.